
int curDivision = 29*timeVar;                      //how many inbetweens are being created between any two keys
ArrayList<pt> keyframes = new ArrayList<pt>(); //arraylist of inbetween frames
ArrayList<Float> angles = new ArrayList<Float>(); //arraylist of the angle of the dancer at each frame
ArrayList<Boolean> rightfoot = new ArrayList<Boolean>(); //an array list of booleans, rightfooted dancer keys are true

float curx=C.P[0].x; //current position of the animating dancer used for camera tracking
float cury=C.P[0].y; 

float getTime(int i) //stubbed time function in case of changing the way time is calculated
{
  return i;
  
}

pt nevillesAlgorithmCall(int i, int j, float eval, pt[] myPoints){ //hub for calculating nevilles algorithm calls
  float x = nevillesAlgorithmX( i, j, eval, myPoints);
  float y = nevillesAlgorithmY( i, j, eval, myPoints);
  pt a = new pt();
  a.x = x;
  a.y = y;
  return a;
  
}

float nevillesAlgorithmX(int i, int j, float eval, pt[] myPoints){//calculate a new point based on the list of given coordinates
  if(j!=i){
    float k = ((getTime(j)-eval)*nevillesAlgorithmX(i,j-1,eval,myPoints) + (eval - getTime(i))*nevillesAlgorithmX(i+1, j, eval,myPoints))/(getTime(j)-getTime(i));
//    println(k);
    return k;
  }
  return myPoints[i].x;
}

float nevillesAlgorithmY(int i, int j, float eval, pt[] myPoints){//calculate a new point based on the list of given coordinates
  if(j!=i){
    return((getTime(j)-eval)*nevillesAlgorithmY(i,j-1,eval,myPoints) + (eval - getTime(i))*nevillesAlgorithmY(i+1, j, eval,myPoints))/(getTime(j)-getTime(i));
  }
  return myPoints[i].y;
}

float nevillesAlgorithmAngle(int i, int j, float eval, float[] angles){//calculate a new angle based on the list of given coordinates
  if(j!=i){
    float k = ((getTime(j)-eval)*nevillesAlgorithmAngle(i,j-1,eval,angles) + (eval - getTime(i))*nevillesAlgorithmAngle(i+1, j, eval,angles))/(getTime(j)-getTime(i));
//    println("angle " + k);
    return k;
  }
  return angles[i];
}

void calcFrames(){
  keyframes = new ArrayList<pt>();
  angles = new ArrayList<Float>();
  //the calculations
  for(int j = 0; j < C.n-1; j++){ //for every key drawn by the user
    for(int i = 1; i < curDivision; i++){ //begin calculating the inbetween frames
      int initialPoint = 0;
      int finalPoint = 0;
      if(C.n < 4){ //if there are less than 4 keys, set up special parameters for nevilles algorithm
        initialPoint = 0;
        finalPoint = C.n-1;
      }
      else if(j == 0){ //if we are drawing the first key, set up special parameters for nevilles algorithm
        initialPoint = 0;
        finalPoint = 3;
      }
      else if(j == C.n-2){ //if drawing the second to last key, set up special parameters for nevilles algorithm
        initialPoint = j-2;
        finalPoint = j+1;
      }
      else{ //else, set up normal parameters consisting of the last through the next two keys
        initialPoint = j-1;
        finalPoint = j+2;
      }
      
      float time = j + -0.5*cos(PI * i/(curDivision)) + 0.5; //calculate the current time based on a sine curve
      
      pt p = nevillesAlgorithmCall(initialPoint,finalPoint,time,C.P);
      
      keyframes.add(p);
      
      float a = nevillesAlgorithmAngle(initialPoint,finalPoint,time,C.w);
      
      angles.add(a);
    }
  }
      
}

void drawFrames(){ //iterate through keyframes to draw each frame as an ellipse, resulting in a path for the dancer
  
      for(int i = 0; i<keyframes.size(); i++){
        if(i%(curDivision/29)< 1){
          pt p = keyframes.get(i);
          float a = angles.get(i);
          //the drawing
          stroke(color(100,100,100));

          pushMatrix();
          translate(p.x, p.y);
          rotate(a);
          pushMatrix(); 
          scale(.4, 1); 
          ellipse(0, 0, 100, 100); 
          popMatrix();
          popMatrix();
        }
    }
}

int animCount = 0; //index of the current frame to draw the animation at
int velocity = 1; //increments animCount, increase to skip frames and increase the velocity of the dancer
void animation(boolean threeD){ //draw the simulated dancer

  if(keyframes.size()>0){
    pt p = keyframes.get(animCount);
    curx = p.x;
    cury = p.y;
    float a = angles.get(animCount);
    if(threeD){
      fill(color(63,20,150)); //fill for 3d drawings
    } else {
      stroke(color(63,20,150)); //strokes for 2d drawings
    }
  
    pt r = new pt(); //supporting foot
    pt l = new pt(); //other foot
    
    int nextStop = animCount/curDivision + 1; //index of key the dancer is headed towards next
    
    float distBackOffX = 0;
    float distBackOffY = 0;
    float distOffX = 0;
    float distOffY = 0;
    if(rightfoot.get(nextStop-1) != rightfoot.get(nextStop)){ //if the last key and the next key have opposite supporting feet
      if(rightfoot.get(nextStop-1)){ 
        distBackOffX = -(C.P[nextStop-1].x - (C.P[nextStop].x+30*sin(C.w[nextStop]))); //find the distance between the supporting foot of the last
        distBackOffY = -(C.P[nextStop-1].y - (C.P[nextStop].y -30*cos(C.w[nextStop]))); //and to where it needs to move in the next key
      
        distOffX = -((C.P[nextStop-1].x-30*sin(C.w[nextStop-1])) - C.P[nextStop].x); //find the distance between the other foot
        distOffY = -((C.P[nextStop-1].y +30*cos(C.w[nextStop-1])) - C.P[nextStop].y);//and where it needs to be to support the next key
      } else {
        distBackOffX = -(C.P[nextStop-1].x - (C.P[nextStop].x-30*sin(C.w[nextStop]))); //reverse trigonometry for reverse feet movement
        distBackOffY = -(C.P[nextStop-1].y - (C.P[nextStop].y +30*cos(C.w[nextStop])));
      
        distOffX = -((C.P[nextStop-1].x+30*sin(C.w[nextStop-1])) - C.P[nextStop].x);
        distOffY = -((C.P[nextStop-1].y -30*cos(C.w[nextStop-1])) - C.P[nextStop].y);
      }
        
    } else { //if foot placement is the same from one key to the next
        if(rightfoot.get(nextStop-1)){ 
          distBackOffX = -(C.P[nextStop-1].x - (C.P[nextStop].x)); //move the supporting foot into its same position
          distBackOffY = -(C.P[nextStop-1].y - (C.P[nextStop].y));
          
          distOffX = -((C.P[nextStop-1].x) - C.P[nextStop].x + 30*sin(C.w[nextStop]) - 30*sin(C.w[nextStop-1])); //move the other foot
          distOffY = -((C.P[nextStop-1].y) - C.P[nextStop].y - 30*cos(C.w[nextStop]) + 30*cos(C.w[nextStop-1]));
        } else {
          distBackOffX = -(C.P[nextStop-1].x - (C.P[nextStop].x)); //move the supporting foot into its same position
          distBackOffY = -(C.P[nextStop-1].y - (C.P[nextStop].y));
          
          distOffX = -((C.P[nextStop-1].x) - C.P[nextStop].x - 30*sin(C.w[nextStop]) + 30*sin(C.w[nextStop-1])); //move the other foot
          distOffY = -((C.P[nextStop-1].y) - C.P[nextStop].y + 30*cos(C.w[nextStop]) - 30*cos(C.w[nextStop-1]));
        }
    }
    
    
    
    float traveled = ((curDivision*nextStop) - (animCount))/(curDivision*1.0); //travel distance between keys, starting at 1 and counting down 0
    if(traveled < 1.0/3){ //final 1/3 of the animation
  
//      r.x = distBackOffX*(1-3*traveled);
//      r.y = distBackOffY*(1-3*traveled);
      r.x = 0.5*((cos(PI*(3*(2.0/3+traveled))))*distBackOffX + distBackOffX); //movement of foot given a cosine function
      r.y = 0.5*((cos(PI*(3*(2.0/3+traveled))))*distBackOffY + distBackOffY);
  
      if(rightfoot.get(nextStop-1) != rightfoot.get(nextStop)){
        l.x = C.P[nextStop].x - C.P[nextStop-1].x; //keeps the other foot in place
        l.y = C.P[nextStop].y - C.P[nextStop-1].y;
      } else {
        if(rightfoot.get(nextStop)){
          l.x = C.P[nextStop].x - 30*sin(C.w[nextStop]) - C.P[nextStop-1].x; //rotation of foot in case of weight switch
          l.y = C.P[nextStop].y + 30*cos(C.w[nextStop]) - C.P[nextStop-1].y;
        } else {
          l.x = C.P[nextStop].x + 30*sin(C.w[nextStop]) - C.P[nextStop-1].x;
          l.y = C.P[nextStop].y - 30*cos(C.w[nextStop]) - C.P[nextStop-1].y;
        }
      }
    } else if (traveled > 2.0/3){//first third of animation
      
      l.x = 0.5*((cos(PI*(3*traveled)))*distOffX + distOffX); //movement of non-supporting foot during beginning of animation
      l.y = 0.5*((cos(PI*(3*traveled)))*distOffY + distOffY);
  
    } else { //middle third of animation
      
      if(rightfoot.get(nextStop-1) != rightfoot.get(nextStop)){
        r.x = C.P[nextStop].x - C.P[nextStop-1].x; //keeps feet in correct position, not moving
        r.y = C.P[nextStop].y - C.P[nextStop-1].y;
      } else {
        if(rightfoot.get(nextStop)){
          r.x = C.P[nextStop].x - 30*sin(C.w[nextStop]) - C.P[nextStop-1].x;//rotation of foot in case of weight switch
          r.y = C.P[nextStop].y + 30*cos(C.w[nextStop]) - C.P[nextStop-1].y;
        } else {
          r.x = C.P[nextStop].x + 30*sin(C.w[nextStop]) - C.P[nextStop-1].x;
          r.y = C.P[nextStop].y - 30*cos(C.w[nextStop]) - C.P[nextStop-1].y;
        }
      }
      
    }
    
    if( rightfoot.get(nextStop-1)){
      if(threeD){ //check for 3D mode
        drawDancer3D(nextStop,p, a, rightfoot.get(nextStop-1),r, l, traveled);
      } else {
        drawDancer(nextStop,p, a, rightfoot.get(nextStop-1),r, l, traveled);
      }
      
    } else { //switch left and right feet as the supporting and non supporting
      if(threeD){
        drawDancer3D(nextStop,p, a, rightfoot.get(nextStop-1),l, r, traveled);
      } else {
        drawDancer(nextStop,p, a, rightfoot.get(nextStop-1),l, r, traveled);
      }
      
    }
    animCount+=velocity;
  }
}

//overload the drawDancer method specifically for the animated version of the dancer
void drawDancer(int stop, pt P, float w, Boolean r, pt ri, pt l, float trans) { // shows dancer in 2D at P with orientation w standing on right foot when r
  pt previous = C.P[stop-1];
  pushMatrix();
  pushMatrix();

  translate(previous.x,previous.y);
  if(trans >= 2.0/3){
  if(r) translate(l.x-30*sin(C.w[stop-1]),l.y+30*cos(C.w[stop-1]));
  else translate(l.x,l.y);
  } else {
    if(r) translate(l.x,l.y);
    else translate(l.x,l.y);
  }

  if(r){ //decide which foor to fill as the supporting foot based on how far along the animation is
    if(trans <=2.0/3){
      fill(63,20,150);
      ellipse(0, 0, 20, 20); // supporting foot
      noFill();
    } else {
      ellipse(0,0,20,20);
    }
  } else {
    if(trans >= 1.0/3){
      fill(63,20,150);
      ellipse(0, 0, 20, 20); // supporting foot
      noFill();
    } else { 
      ellipse(0, 0, 20, 20); 
    }
  }
  popMatrix();
  pushMatrix(); 

  translate(previous.x,previous.y);
  if(trans >=2.0/3){
  if(r) translate(ri.x,ri.y);
  else translate(ri.x+30*sin(C.w[stop-1]),ri.y-30*cos(C.w[stop-1]));
  } else {
    if(r) translate(ri.x,ri.y);
    else translate(ri.x,ri.y);
  }
  
  scale(.2, .2);
  if(r){
    if(trans >= 1.0/3){
      fill(63,20,150);
      ellipse(0, 0, 100, 100); // other foot
      noFill();
    } else { 
      ellipse(0, 0, 100, 100); 
    }
  } else {
    if(trans <=2.0/3){
      fill(63,20,150);
      ellipse(0, 0, 100, 100); // other foot
      noFill();
    } else {
      ellipse(0,0,100,100);
    }
  }
  popMatrix(); // other foot
  
  translate(P.x, P.y);
  rotate(w);
  pushMatrix(); 
  scale(.4, 1); 
  ellipse(0, 0, 100, 100); 
  popMatrix();
  
  pushMatrix(); 
  translate(5, 0); 
  scale(.45, .35); 
  ellipse(0, 0, 100, 100); 
  popMatrix(); // head
  popMatrix();
}

void drawDancer3D(int stop, pt P, float w, Boolean r, pt ri, pt l, float trans) { // shows dancer in 3D at P with orientation w standing on right foot when r
  pt previous = C.P[stop-1];
  noStroke();
  pushMatrix();

  translate(0,0,50);
  
  float globalrix;
  float globalriy;
  float globalriz = -50;
  float globallx;
  float globally;
  float globallz = -50;
  
  if(trans >= 2.0/3){ //calculate the global coordinates for the feet to draw the legs toward
    if(r){
      globalrix = ri.x + previous.x;
      globalriy = ri.y + previous.y;
      globallx = l.x - 30*sin(C.w[stop-1]) + previous.x;
      globally = l.y + 30*cos(C.w[stop-1]) + previous.y;
    } else {
      globalrix = ri.x + 30*sin(C.w[stop-1]) + previous.x;
      globalriy = ri.y - 30*cos(C.w[stop-1]) + previous.y;
      globallx = l.x + previous.x;
      globally = l.y + previous.y;
    }
  } else if(trans<=1.0/3){
    if(r){
      globalrix = ri.x + previous.x;
      globalriy = ri.y + previous.y;
      globallx = l.x + previous.x;
      globally = l.y + previous.y;
    } else {
      globalrix = ri.x + previous.x;
      globalriy = ri.y + previous.y;
      globallx = l.x  + previous.x;
      globally = l.y  + previous.y;
    }
  
  } else {
      if(r){
      globalrix = l.x + previous.x;
      globalriy = l.y + previous.y;
      globallx = ri.x  + previous.x;
      globally = ri.y  + previous.y;
    } else {
      globalrix = l.x  + previous.x;
      globalriy = l.y  + previous.y;
      globallx = ri.x + previous.x;
      globally = ri.y + previous.y;
    }
  }
  
  float globalhipleftx= P.x + 25*sin(-w); //calculate the global coordinates of the hips to draw the legs from
  float globalhiplefty= P.y + 25*cos(-w);
  
  float globalhiprightx= P.x - 25*sin(-w);
  float globalhiprighty= P.y - 25*cos(-w);
  
  float distancex = globalhipleftx - globallx; //calculate the distance from a hip to its corresponding foot
  float distancey = globalhiplefty - globally;
  
  float distance2x = globalhiprightx - globalrix;
  float distance2y = globalhiprighty - globalriy;
  float distancelz;
  float distancerz;
//  float distancez = -100 + 20;
  
  if(r){ // lift the legs using a sine function with respect to how far its traveled between keys
    if(trans <= 1.0/3){
      distancerz = -80 + 80*abs(-sin(3*PI*(1-trans)))/2;
      distancelz = -80;
    } else if(trans >= 2.0/3) {
      distancelz = -80 + 80*abs(-sin(3*PI*(trans)))/2;
      distancerz = -80;
    } else {
      distancelz = -80;
      distancerz = distancelz;
    }
  } else {
    if(trans <= 1.0/3){
      distancelz = -80 + 80*abs(-sin(3*PI*(1-trans)))/2;
      distancerz = -80;
    } else if(trans >= 2.0/3) {
      distancerz = -80 + 80*abs(-sin(3*PI*(trans)))/2;
      distancelz = -80;
    } else {
      distancelz = -80;
      distancerz = distancelz;
    }
  }

  pushMatrix();
  translate(previous.x,previous.y,0);
  if(trans >= 2.0/3){ //translate the foot into position
    if(r) translate(l.x-30*sin(C.w[stop-1]),l.y+30*cos(C.w[stop-1]),distancelz+80);
    else translate(l.x,l.y,distancelz+80);
  } else {
    if(r) translate(l.x,l.y,distancelz+80);
    else translate(l.x,l.y,distancelz+80);
  }
  translate(0, 0, -100); 
  rotate(w);
  scale(.25, .1, .1); 
  sphere(50); 
  popMatrix(); // supporting foot

  pushMatrix();
  translate(previous.x,previous.y,0);
  if(trans >=2.0/3){
    if(r) translate(ri.x,ri.y,distancerz+80);
    else translate(ri.x+30*sin(C.w[stop-1]),ri.y-30*cos(C.w[stop-1]),distancerz+80);
  } else {
    if(r) translate(ri.x,ri.y,distancerz+80);
    else translate(ri.x,ri.y,distancerz+80);
  }
  
  translate(0,0,-100);
  rotate(w);
  scale(.25, .1, .1); 
  sphere(50); 
  popMatrix(); // other foot
  
  translate(P.x, P.y, 0); 
  rotate(w); // align body
  
  pushMatrix(); 
  scale(.4, .6, 1); 
  sphere(50); 
  popMatrix(); // body
  
  pushMatrix(); 
  translate(10, 0, 65); 
  scale(.35, .35, .50);  
  sphere(50);  
  popMatrix(); // head
  
  pushMatrix();
  translate(0,-25,-20);
  scale(.2, .2, .2);
  sphere(50);
  popMatrix(); //left hip
  
  pushMatrix();
  translate(0,25,-20);
  scale(.2, .2, .2);
  sphere(50);
  popMatrix(); //right hip
  
  popMatrix();
  
  translate(0,0,50);

  for(int i = 0; i < 10; i++){ //draws spheres along the distance from hip to foot to form leg
    pushMatrix();
    translate((globalhipleftx-distancex*i/10),(globalhiplefty-distancey*i/10),(-20)+distancelz*i/10);
    sphere(5);
    popMatrix();
  }
  
  for(int i = 0; i < 10; i++){
    pushMatrix();
    translate((globalhiprightx-distance2x*i/10),(globalhiprighty-distance2y*i/10),(-20)+distancerz*i/10);
    sphere(5);
    popMatrix();
  }
  
}

